package com.lihepeng.leecode.array2;

public class MaxPQ <Key extends Comparable>{
    private Key[] pq;
    private int N =0;

    public MaxPQ(int cap) {
        this.N = cap;
        pq = (Key[]) new Comparable[cap];
    }
    // 返回最大的数值
    public Key max(){
        return pq[0];
    }
    // 插入元素
    public void insert(Key e){
        N++;
        pq[N] = e;
        swim(N);

    }
    // 删除堆顶元素
    public Key delMax(){
        Key max = pq[N];
        exch(1,N);
        pq[N]=null;
        N--;
        sink(1);
        return max;
    }
    private int parent(int i){
        return i/2;
    }
    private int leftChild(int i) {
        return i*2;
    }
    private int rightChild(int i) {
        return i*2+1;
    }

    /**
     * 上浮操作
     * @param k 
     */
    private void swim(int k){
        while (k>1 && less(parent(k),k)) {
            // 当元素节点 大于父节点的时候进行上浮操作
            exch(parent(k),k);
            k = parent(k);
        }
    }
    private void sink(int k){
        // 沉到堆低 就不能沉了
        while (leftChild(k) <N) {
            //先假设左边的元素比较大
            int older = leftChild(k);
            if (rightChild(k)<=N && less(older,rightChild(k))){
                older = rightChild(older);
                if (less(older,k)){
                    break;
                }
                exch(k,older);
                k = older;
            }
        }
    }

    private void exch(int i,int j){
        Key key = pq[i];
        pq[i] = pq[j];
        pq[j] = key;
    }

    /**
     * 返回 i所在的元素是不是比j所在的元素小
     * @return
     */
    private boolean less(int i,int j ){
        return pq[i].compareTo(pq[j])<0;
    }

}
